'''
Created on Nov 14, 2013

@author: root
'''
import unittest
import ej3Dijkstra.grafoDijkstrado
import colecciones.DefinicionDeGrafo.recorridos
import colecciones.DefinicionDeGrafo.arista

class MejorCaminoDfsAdap(colecciones.DefinicionDeGrafo.recorridos.Recorridos):
    '''
    Clase MejorCaminoDfsAdap: hereda de recorridos
    '''
    def buscar_1_camino(self,grafo,origen, destino, camino):
        '''
        actualiza una lista de vertices con el recorrido del mejor camino del grafo
        recibido como parametro desde el vertice origen hasta el vertice destino
        devuelve el producto de los pesos de las aristas
        '''
        visitado = [False]*grafo.getListaDeVertices().getTamanio()#la otra inicializacion del vector no funciona
        
        return self.__recBuscar_1_camino__(
                   colecciones.DefinicionDeGrafo.arista.Arista(
                                   origen,1), camino, visitado,destino)
            
    def __recBuscar_1_camino__(self,a_origen,camino,visitado,destino):
        camino.agregar(a_origen.getVerticeDestino(),camino.getTamanio())#guarda en la lista
        visitado[a_origen.getVerticeDestino().getPosicion()]=True#sino recorre
        prodPeso=a_origen.getPeso()
        if a_origen.getVerticeDestino().__cmp__(destino)==0:
            return a_origen.getPeso() #si encontro destino
        else:
            recorredor = a_origen.getVerticeDestino().getListaDeAdyacentes().recorredor()
            recorredor.comenzar()
            maxPeso=0
            mP=None
            while not recorredor.fin():
                ady = recorredor.elemento()
                if not visitado[ady.getVerticeDestino().getPosicion()]:
                    if ady.getPeso()>maxPeso:
                        maxPeso=ady.getPeso()
                        mP=ady
                recorredor.proximo()
            return prodPeso*self.__recBuscar_1_camino__(mP,camino,visitado,destino)
    

class Test(unittest.TestCase):


    def testInit(self):
        self.assertIsInstance(ej3Dijkstra.grafoDijkstrado.GrafoDijkstrado(), ej3Dijkstra.grafoDijkstrado.GrafoDijkstrado,"Verifica inicializacion")
        grafo=ej3Dijkstra.grafoDijkstrado.GrafoDijkstrado()
        grafo.agregarVertice(
                 colecciones.DefinicionDeGrafo.vertice.Vertice(0,
                          colecciones.listaEnlazada.ListaEnlazada()
                                    )
                            )
        grafo.agregarVertice(
                 colecciones.DefinicionDeGrafo.vertice.Vertice(1,
                          colecciones.listaEnlazada.ListaEnlazada()
                                    )
                          )
        grafo.agregarVertice(
                 colecciones.DefinicionDeGrafo.vertice.Vertice(2,
                          colecciones.listaEnlazada.ListaEnlazada()
                                    )
                          )
        grafo.agregarVertice(
                 colecciones.DefinicionDeGrafo.vertice.Vertice(3,
                          colecciones.listaEnlazada.ListaEnlazada()
                                    )
                          )
        grafo.agregarVertice(
                 colecciones.DefinicionDeGrafo.vertice.Vertice(4,
                          colecciones.listaEnlazada.ListaEnlazada()
                                    )
                          )
        grafo.conectar(grafo.vertice(0), grafo.vertice(2), 1)# 0 con 2 peso1
        grafo.conectar(grafo.vertice(1), grafo.vertice(0), 3)# 1 con 0 peso3
        grafo.conectar(grafo.vertice(1), grafo.vertice(2), 2)# 1 con 2 peso2
        grafo.conectar(grafo.vertice(1), grafo.vertice(3), 4)# 1 con 3 peso4
        grafo.conectar(grafo.vertice(2), grafo.vertice(3), 7)# 2 con 3 peso7
        grafo.conectar(grafo.vertice(2), grafo.vertice(4), 4)# 2 con 4 peso4
        grafo.conectar(grafo.vertice(3), grafo.vertice(4), 3)# 3 con 4 peso3
        grafo.conectar(grafo.vertice(3), grafo.vertice(0), 1)# 3 con 0 peso1
        grafo.conectar(grafo.vertice(4), grafo.vertice(0), 6)# 4 con 0 peso6
        grafo.conectar(grafo.vertice(4), grafo.vertice(1), 2)# 4 con 1 peso2
        grafo.conectar(grafo.vertice(4), grafo.vertice(3), 2)# 4 con 3 peso2
        self.assertIsInstance(grafo, ej3Dijkstra.grafoDijkstrado.GrafoDijkstrado,"Verifica inicializacion")

    def testbuscar_1_camino(self):
        self.assertIsInstance(ej3Dijkstra.grafoDijkstrado.GrafoDijkstrado(), ej3Dijkstra.grafoDijkstrado.GrafoDijkstrado,"Verifica inicializacion")
        grafo=ej3Dijkstra.grafoDijkstrado.GrafoDijkstrado()
        grafo.agregarVertice(
                 colecciones.DefinicionDeGrafo.vertice.Vertice(0,
                          colecciones.listaEnlazada.ListaEnlazada()
                                    )
                            )
        grafo.agregarVertice(
                 colecciones.DefinicionDeGrafo.vertice.Vertice(1,
                          colecciones.listaEnlazada.ListaEnlazada()
                                    )
                          )
        grafo.agregarVertice(
                 colecciones.DefinicionDeGrafo.vertice.Vertice(2,
                          colecciones.listaEnlazada.ListaEnlazada()
                                    )
                          )
        grafo.agregarVertice(
                 colecciones.DefinicionDeGrafo.vertice.Vertice(3,
                          colecciones.listaEnlazada.ListaEnlazada()
                                    )
                          )
        grafo.agregarVertice(
                 colecciones.DefinicionDeGrafo.vertice.Vertice(4,
                          colecciones.listaEnlazada.ListaEnlazada()
                                    )
                          )
        grafo.conectar(grafo.vertice(0), grafo.vertice(2), 1)# 0 con 2 peso1
        grafo.conectar(grafo.vertice(1), grafo.vertice(0), 3)# 1 con 0 peso3
        grafo.conectar(grafo.vertice(1), grafo.vertice(2), 2)# 1 con 2 peso2
        grafo.conectar(grafo.vertice(1), grafo.vertice(3), 4)# 1 con 3 peso4
        grafo.conectar(grafo.vertice(2), grafo.vertice(3), 7)# 2 con 3 peso7
        grafo.conectar(grafo.vertice(2), grafo.vertice(4), 4)# 2 con 4 peso4
        grafo.conectar(grafo.vertice(3), grafo.vertice(4), 3)# 3 con 4 peso3
        grafo.conectar(grafo.vertice(3), grafo.vertice(0), 1)# 3 con 0 peso1
        grafo.conectar(grafo.vertice(4), grafo.vertice(0), 6)# 4 con 0 peso6
        grafo.conectar(grafo.vertice(4), grafo.vertice(1), 2)# 4 con 1 peso2
        grafo.conectar(grafo.vertice(4), grafo.vertice(3), 2)# 4 con 3 peso2
        recorrido=MejorCaminoDfsAdap()
        camino=colecciones.listaEnlazada.ListaEnlazada()
        recorrido.buscar_1_camino(grafo, grafo.vertice(4), grafo.vertice(3),camino)
        self.assertEquals(camino.elemento(1),grafo.vertice(0),"Verifica camino")
        self.assertEquals(camino.elemento(2),grafo.vertice(2),"Verifica camino")
        self.assertEquals(camino.elemento(3),grafo.vertice(3),"Verifica camino")
        print recorrido.buscar_1_camino(grafo, grafo.vertice(4), grafo.vertice(3),camino)
        self.assertEquals(recorrido.buscar_1_camino(grafo, grafo.vertice(4), grafo.vertice(3),camino), 42, "El producto de aristas")

if __name__ == "__main__":
    #import sys;sys.argv = ['', 'Test.testName']
    unittest.main()